The amount of data being stored and transmitted over networks continues to increase. Data streams are often encoded to reduce the amount of required memory. One example of data compression involves identifying patterns of symbols, such as letters, that are transmitted frequently. Instead of retransmitting the same patterns of symbols, the pattern may be transmitted once. When that same pattern is identified again, a reference to the previous pattern may be transmitted instead of repeating the pattern. Because the reference, or pointer, to the previous pattern is shorter than retransmitting the pattern itself, the data stream can be compressed.
One example of a type of data compression is the GZIP format, which is used to store system images for routers and switches, to transmit web pages, voice, audio, text, and other data, and in a variety of other applications. GZIP uses a sliding window protocol for rebuilding bytes of data and Huffman encoded commands that control operation of the sliding window protocol. One particular example of Huffman encoding is canonical Huffman encoding, which provides enhanced data compression.
Canonical Huffman encoding involves, generally, encoding a bit stream at a transmitter by creating a codebook that describes how the bit stream has been encoded. The encoded bit stream is transmitted to a receiver along with the codebook, and the receiver uses the codebook to recreate the bit stream from the encoded bit stream. In particular, canonical Huffman encoding uses bit lengths to represent characters in the codebook. By transmitting the lengths in a defined order, the receiver can recreate characters using the transmitted lengths.
The process of recreating a codebook by a receiver and decoding a bit stream from transmitted lengths requires time and processing resources. With increased transmission of encoded data, data recipients spend an increasing amount of their processing resources creating decoding tables and decoding bit streams into usable forms. Creating a decoding table using software, for example, requires additional processing time that can delay system responsiveness.
The present disclosure uses a programmable priority encoder to create a canonical Huffman decoding table in a ternary content-addressable memory and overcome one or more problems discussed above, among others.
Like reference numbers and designations in the various drawings indicate like elements.